class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        // 优化
        /*
            [3, 3, 7, 7, 10, 11, 11]
             0  1  2  3   4   5   6
            left     mid         right
            10 是答案
            在他的左边每对数字下标都满足[偶数，奇数]
            在他的右边每对数字下标都满足[奇数，偶数]
            mid 是奇数，nums[mid] == nums[mid - 1] ---> left = mid + 1
            mid 是偶数，nums[mid] == nums[mid + 1] ---> left = mid + 2
        */
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = (left + right) / 2;
            // mid 如果是奇数，mid ^ 1 就是偶数
            // mid 如果是偶数，mid ^ 1 就是奇数
            if(nums[mid] != nums[mid ^ 1])
                right = mid;
            else
            {
                left = mid + 1;
                if(mid % 2 == 0)
                    left++;
            }


            // if(mid % 2 == 0)
            // {
            //     if(nums[mid] == nums[mid + 1])
            //         left = mid + 2;
            //     else
            //         right = mid;
            // }
            // else if(mid % 2 != 0)
            // {
            //     if(nums[mid] == nums[mid - 1])
            //         left = mid + 1;
            //     else
            //         right = mid - 1;
            // }
        }
        return nums[left];


        // 时间复杂度是O(n)
        // int n = nums.size();
        // int left = 0, right = 1;
        // while(right < n)
        // {
        //     if(nums[left] != nums[right])
        //         return nums[left];
        //     left += 2;
        //     right += 2;
        // }
        // return nums[left];


        // 时间复杂度也是O(n)
        // int ret = 0;
        // for(int &x : nums) ret ^= x;
        // return ret; 
    }
};